package me.eg.forth;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 130. 被围绕的区域
 * <p>
 * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，
 * 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
 * <p>
 * https://leetcode-cn.com/problems/surrounded-regions/
 */
public class SurroundedRegions {
    private char[][] board;
    private int m;
    private int n;
    private boolean[][] visited;
    private int[][] direction;

    public void solve(char[][] board) {
        // 思路：
        // 1、O 和 O 之间连边，找所有 O 的连通块
        // 2、目标连通块：找边界都是 X，不是矩阵边界
        // 3、将目标连通块的 O 改成 X

        this.board = board;
        this.m = board.length;
        this.n = board[0].length;
        this.visited = new boolean[m][n];
        this.direction = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

        List<Pair<Integer, Integer>> allTargets = new ArrayList<>();
        for (int x = 0; x < m; x++) {
            for (int y = 0; y < n; y++) {
                if (visited[x][y]) continue;
                if (board[x][y] == 'X') continue;

//                解法一：广度优先遍历
//                List<Pair<Integer, Integer>> points = bfs(x, y);
//                if (points != null) {
//                    allTargets.addAll(points);
//                }

                // 解法二：深度优先遍历
                List<Pair<Integer, Integer>> points = new ArrayList<>();
                if (!dfs(x, y, points)) {
                    allTargets.addAll(points);
                }
            }
        }

        for (Pair<Integer, Integer> p : allTargets) {
            board[p.getKey()][p.getValue()] = 'X';
        }
    }

    /**
     * 解法一：广度优先遍历
     *
     * @param x
     * @param y
     * @return
     */
    private List<Pair<Integer, Integer>> bfs(int x, int y) {
        boolean isLinkBorder = false;
        List<Pair<Integer, Integer>> points = new ArrayList<>();

        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        visited[x][y] = true;
        queue.offer(new Pair<>(x, y));
        while (!queue.isEmpty()) {
            Pair<Integer, Integer> p = queue.poll();
            points.add(p);

            for (int d = 0; d < 4; d++) {
                int nx = p.getKey() + direction[d][0];
                int ny = p.getValue() + direction[d][1];

                if (!isValid(nx, ny)) {
                    isLinkBorder = true; // 触碰到边界
                    continue;
                }
                if (visited[nx][ny]) continue;
                if (board[nx][ny] == 'X') continue;

                visited[nx][ny] = true;
                queue.offer(new Pair<>(nx, ny));
            }
        }

        if (!isLinkBorder) return points;
        else return null;
    }

    /**
     * 解法二：深度优先遍历
     *
     * @param x
     * @param y
     * @param points
     * @return
     */
    private boolean dfs(int x, int y, List<Pair<Integer, Integer>> points) {
        visited[x][y] = true;
        points.add(new Pair<>(x, y));

        boolean isLinkBorder = false;
        for (int d = 0; d < 4; d++) {
            int nx = x + direction[d][0];
            int ny = y + direction[d][1];

            if (!isValid(nx, ny)) {
                isLinkBorder = true;
                continue;
            }
            if (visited[nx][ny]) continue;
            if (board[nx][ny] == 'X') continue;

            isLinkBorder = dfs(nx, ny, points) || isLinkBorder;
        }
        return isLinkBorder;
    }

    private boolean isValid(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}